package com.berchen.test;

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;

/**
 * 分治算法排序
 */
public class MergeSort {
    public static void main(String[] args) {

        int size=800;
        int[] testArr=new int[size];
        for(int i =0;i<testArr.length;i++){
            testArr[i]=(int)(Math.random()*size);
        }

        Instant start=Instant.now();
        fen(testArr,0,size-1,new int[testArr.length]);
        Instant end=Instant.now();
        System.out.println(Duration.between(start,end).toMillis()); //15
        System.out.println(Arrays.toString(testArr));
    }
    public static void fen(int[] arr,int start,int end ,int [] temp){
        if(start<end){
            int mid=(start+end)/2;
            fen(arr,start,mid,temp);
            fen(arr,mid+1,end,temp);
            merge(arr,start,mid,end,temp);
        }
    }
    public static void merge(int[] arr,int start,int mid,int end,int[] temp){

        int l=start;
        int r=mid+1;
        int tempIndex=0;

        while (l<=mid&&r<=end){
            if(arr[l]<arr[r]){
                temp[tempIndex++]=arr[l++];
            }else {
                temp[tempIndex++]=arr[r++];
            }
        }
        while (l<=mid){
            temp[tempIndex++]=arr[l++];
        }
        while (r<=end){
            temp[tempIndex++]=arr[r++];
        }
        tempIndex=0;
        for(int i=start;i<=end;i++){
            arr[i]=temp[tempIndex++];
        }
    }
}
